1. Technical Field
The present invention is directed to accesses to memory by input/output devices. More specifically, the present invention is directed to a system and method of improving fault-based multi-page pre-fetches.
2. Description of Related Art
Operating systems (OSs) as well as application programs are increasingly getting larger in size. Correspondingly, the amount of physical memory (i.e., random access memory or RAM) space they need to properly execute is also increasingly growing larger. However, to provide enough RAM space for simultaneous executions of an OS and an indeterminate number of application programs is unfeasible. Consequently, virtual memory is used.
Virtual memory is imaginary memory and is supported by most operating systems. (OSs and application programs will henceforth be referred to as programs.) Each executing program, which includes code and data, is allocated a certain amount of virtual memory space. For example in Windows-based systems, each executing program is allocated 2 GB of virtual memory space. Thus, virtual memory is ostensibly limitless.
Each executing program is also allocated a certain amount of RAM space since a program must physically be in RAM in order to execute. However, allocated virtual memory space is usually much larger than allocated RAM space. Hence, a program that fits into its allocated virtual memory space may not all fit (especially its data) into its allocated RAM space. Since virtual memory does not really exist, the portion of the program that does not fit into the RAM is placed in a storage device (e.g., disk, tape, cartridge etc.). This allows the system to nonetheless execute the program by copying into RAM sections of the program needed at any given point during its execution.
To facilitate copying sections of a program into RAM, the operating system divides the virtual memory into virtual pages and the RAM into physical pages (also known as page frames). Each virtual page contains a fixed amount of space. Each physical page contains an equally fixed amount of space. Addresses of virtual pages are called virtual addresses and those of the physical pages are called physical addresses.
Thus, a page of data may either be in RAM or in a storage device. To keep track of which pages are in RAM, a virtual memory manager (VMM) is used. The VMM is a process that is primarily responsible for managing the use of both the RAM and the virtual memory. To do so, the VMM keeps track of each page that is in RAM and swaps pages to and from the storage device both on demand and routinely.
An on-demand swap occurs when an executing instruction of a program requests data that is not already in RAM. Particularly, when requesting data an executing program will provide the virtual address of the data. The virtual address is then translated into its physical address equivalent. If after the address translation the page on which the data is located is identified as being absent from the RAM, a page-fault exception is raised. A page fault results in switching immediately to a page fault handler. Using a replacement algorithm (e.g., a least recently used algorithm or LRU) a page of data in RAM is transferred onto the storage device. The page fault handler then loads the page onto which the requested data is located into the now-vacant page in RAM and, upon return, the instruction that generated the page fault is re-executed. This is a relatively fast process, but accumulating many page faults can have a drastic impact on performance.
Consequently, to reduce the number of page faults that may occur during the execution of a program, a method known as read-ahead or data pre-fetching is used. As the name suggests, data pre-fetching involves obtaining data before it is needed. Various types of data pre-fetching techniques have been developed. One of these techniques is called spatial data pre-fetching.
Spatial data pre-fetching is based on the likelihood that once data is referenced, nearby data is also likely to be referenced. That is, the decision to pre-fetch data is determined by the current data block access (e.g., fetching the data block adjacent to the data block currently being accessed).
Spatial data pre-fetching works splendidly when data is being read sequentially. For example, after two consecutive page faults of sequentially stored data, a block of sequential pages of data will be pre-fetched through normal data read-ahead. Hence, if future referenced pages are part of the pre-fetched block, which is highly likely when data is being read sequentially, the data will have already been in RAM when needed.
However, if data is being read randomly, spatial data pre-fetching may not work as well. For example, suppose an executing program is randomly reading data. Suppose further that the executing program makes a request to read a certain amount of data that resides on two sequential pages. If the data is not already in RAM, two page faults will be raised in order to load the two pages in the RAM. Because the pages are sequential, the system may infer that data is being read sequentially; and hence, pre-fetch a block of sequential pages of data. Since data is being read randomly, it is highly unlikely that future needed data will be on the pre-fetched block of pages. Thus, the block of pages may have been pre-fetched in vain and the physical pages onto which they are placed wasted. As will be explained later, continually pre-fetching unneeded pages of data may place an undue pressure on RAM space.
Thus a need exists for a system and method of improving multi-page fault-based data pre-fetches.